package com.future;

import java.util.HashMap;
import java.util.Map;

/**
 * Description: 523. 连续的子数组和
 * <p>
 * 给你一个整数数组 nums 和一个整数 k ，编写一个函数来判断该数组是否含有同时满足下述条件的连续子数组：
 * <p>
 * 子数组大小 至少为 2 ，且
 * 子数组元素总和为 k 的倍数。
 * 如果存在，返回 true ；否则，返回 false 。
 * <p>
 * 如果存在一个整数 n ，令整数 x 符合 x = n * k ，则称 x 是 k 的一个倍数。0 始终视为 k 的一个倍数。
 * <p>
 *  
 * <p>
 * 示例 1：
 * <p>
 * 输入：nums = [23,2,4,6,7], k = 6
 * 输出：true
 * 解释：[2,4] 是一个大小为 2 的子数组，并且和为 6 。
 * 示例 2：
 * <p>
 * 输入：nums = [23,2,6,4,7], k = 6
 * 输出：true
 * 解释：[23, 2, 6, 4, 7] 是大小为 5 的子数组，并且和为 42 。
 * 42 是 6 的倍数，因为 42 = 7 * 6 且 7 是一个整数。
 * 示例 3：
 * <p>
 * 输入：nums = [23,2,6,4,7], k = 13
 * 输出：false
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/continuous-subarray-sum
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @author weiruibai.vendor
 * Date: 2023/3/17 09:33
 */
public class Solution_523 {

    private static Solution_523 getInstance() {
        return new Solution_523();
    }

    public static void main(String[] args) {
        int[] nums = new int[]{23, 2, 6, 4, 7};
        int k = 6;

        nums = new int[]{23, 2, 4, 6, 6};
        k = 7;

        nums = new int[]{5, 0, 0, 0};
        k = 3;

        nums = new int[]{23, 2, 6, 4, 7};
        k = 13;

        nums = new int[]{0};
        k = 1;
        nums = new int[]{23, 6, 9};
        k = 6;

        int[][] arr = new int[][]{
                {23, 2, 4, 6, 6},
                {23, 2, 6, 4, 7},
                {5, 0, 0, 0},
                {23, 2, 6, 4, 7},
                {0},
                {23, 6, 9},
                {2, 4, 3},
                {1, 3, 6, 0, 9, 6, 9},
                {5, 0, 0, 0}

        };
        int[] ks = new int[]{
                6, 7, 3, 13, 1, 6, 6, 7, 3
        };

        for (int i = 0; i < arr.length; i++) {
            nums = arr[i];
            k = ks[i];
            System.out.println("正确" + getInstance().checkSubarraySum(nums, k));
            System.out.println("对比" + getInstance().checkSubarraySum_v3(nums, k));
            System.out.println("===========");
        }

    }

    /**
     * 【同余定理】 【哈希表】【简化前缀和】
     * <p>
     * 同余定理：如果两个整数m、n满足n-m能被k整除，那么n和m对k同余
     * <p>
     * 即 ( pre(j) - pre (i) ) % k == 0 则 pre(j) % k == pre(i) % k
     * <p>
     * 推导 => pre (i) % k = (a0 + a1 + ... + ai) % k = (a0 % k + a1 % k + ... ai % k ) % k （该推导在简化前缀和的时候有用，说明当前前缀和 % k 不会影响后面的前缀和 % k ）
     * <p>
     * 哈希表 存储 Key ：pre(i) % k
     * Value： i
     * <p>
     * 遍历过程：
     * <p>
     * 计算前缀和 pre( j ) % k
     * <p>
     * 当pre(j) % k 在哈希表中已存在，则说明此时存在 i 满足 pre(j) % k == pre(i) % k ( i < j )
     * <p>
     * HashMap里，已知Key，可以取到Value 即i的值， 最后 判断 j - i >= 2 是否成立 即可
     * <p>
     * 当 pre(j) % k 不存在于哈希表，则将 (pre(j) % k, j ) 存入哈希表
     * 因在计算 pre(i) = (pre(i-1) + nums[i]) % k 时，pre(i) 只与上一个状态有关
     * <p>
     * 故可以直接用变量pre 替代数组。 那么 求前缀和 % k 的公式就简化为 题解代码中的 remainder = (remainder + nums[i]) % k;
     *
     * @param nums
     * @param k
     * @return
     */
    public boolean checkSubarraySum_v3(int[] nums, int k) {
        int N = nums.length;
        if (N < 2) {
            return false;
        }
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, -1);
        int preSum = 0;
        for (int i = 0; i < N; i++) {
            preSum = (preSum + nums[i]) % k;
            if (map.containsKey(preSum)) {
                Integer index = map.get(preSum);
                if (i - index > 1) {
                    return true;
                }
            } else {
                map.put(preSum, i);
            }
        }
        return false;
    }

    /**
     * @param nums
     * @param k
     * @return
     */
    public boolean checkSubarraySum(int[] nums, int k) {
        int N = nums.length;
        for (int i = 0; i < N; i++) {
            int sum = 0;
            for (int j = i; j >= 0; j--) {
                sum += nums[j];
                if (i - j >= 1 && sum % k == 0) {
                    return true;
                }
            }
        }
        return false;
    }
}
